iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
自我挑戰組

30天初步了解自然語言處理-自學筆記系列 第 8

[Day8] 詞性標注(三)-Viterbi 演算法

  • 分享至 

  • xImage
  •  

一. Viterbi 演算法

因為若要一條條計算每個path的話會花許多時間,利用Dynamic Programming的方法通常會先將前一次狀態的結果存起來,再計算下一個狀態時,再將前一個狀態的結果取出來,可以降低時間複雜度。那如何保留前一個狀態的結果,下面我以前一篇的天氣當例子,當水草當天都為Dry時,哪種天氣組合的機率最大例子:

假設我們有HMM需要的三種矩陣:
https://ithelp.ithome.com.tw/upload/images/20210906/20140426PGWQ1uBvgX.png

  1. 初始狀態:
    https://ithelp.ithome.com.tw/upload/images/20210907/20140426Cbm0MnJQMd.png

    • 在為晴天的狀況下綠色Dry的機率為 0.4(初始的機率)x 0.6(晴天對Dry的機率) = 0.024
    • 在為雨天的狀況下綠色Dry的機率為 0.6(初始的機率)x 0.1(晴天對Dry的機率) = 0.06
  2. 計算第二個Dry上半部分的狀態:
    https://ithelp.ithome.com.tw/upload/images/20210907/20140426OxXnCd4K2n.png

    • 前一天為晴天,今天又為晴天的機率,並且為Dry的機率為 0.024(上一個狀態的機率) * 0.6(前一天為晴天後一天又為晴天的機率) * 0.6(晴天對Dry的機率) = 0.00864
    • 前一天為雨天,今天為雨天的機率,並且為Dry的機率為 0.06(上一個狀態的機率) * 0.3(前一天為雨天後一天又為晴天的機率) * 0.1(晴天對Dry的機率) = 0.0018
    • 接者就是Viterbi 演算法的精髓~紀錄當前最大的機率:
      max(0.00864, 0.0018) = 0.00864
  3. 計算第二個Dry下半部分的狀態:
    https://ithelp.ithome.com.tw/upload/images/20210907/201404266GcB3iP76H.png

    • 前一天為晴天,今天為雨天的機率,並且為Dry的機率為 0.024(上一個狀態的機率) * 0.4(前一天為晴天後一天為雨天的機率) * 0.6(雨天對Dry的機率) = 0.00144
    • 前一天為雨天,今天為晴天的機率,並且為Dry的機率為 0.06(上一個狀態的機率) * 0.7(前一天為雨天後一天又為雨天的機率) * 0.1(雨天對Dry的機率) = 0.0042
    • 紀錄當前最大的機率:
      max(0.00144, 0.0042) = 0.0042
    • P.S. Viterbi 演算法會多一個table去記錄目前連結到這個node的前一個node,用此來記錄經過這個node的最大path,下面的圖我會多紀錄這個node的前一個node
  4. 計算第三個Dry上半部分的狀態:
    https://ithelp.ithome.com.tw/upload/images/20210907/20140426DEu8lf4hg3.png

    • 前一天為晴天,今天又為晴天的機率,並且為Dry的機率為 0.00864(上一個狀態的機率) * 0.6(前一天為晴天後一天又為晴天的機率) * 0.6(晴天對Dry的機率) = 0.0031104
    • 前一天為晴天,今天為雨天的機率,並且為Dry的機率為 0.0042(上一個狀態的機率) * 0.3(前一天為雨天後一天為晴天的機率) * 0.6(晴天對Dry的機率) = 0.000756
    • 紀錄當前最大的機率:
      max(0.0031104, 0.000756) = 0.0031104
  5. 計算第三個Dry下半部分的狀態:
    https://ithelp.ithome.com.tw/upload/images/20210907/20140426Hff3j4S8CB.png

    • 前一天為晴天,今天為雨天的機率,並且為Dry的機率為 0.00864(上一個狀態的機率) * 0.4(前一天為晴天後一天為雨天的機率) * 0.1(雨天對Dry的機率) = 0.0003456
    • 前一天為雨天,今天為雨天的機率,並且為Dry的機率為 0.0042(上一個狀態的機率) * 0.7(前一天為雨天後一天又為雨天的機率) * 0.1(雨天對Dry的機率) = 0.000294
    • 紀錄當前最大的機率:
      max(0.0003456, 0.000294) = 0.0003456
  6. 最後狀態回如下圖:
    https://ithelp.ithome.com.tw/upload/images/20210907/20140426YYhPDqZrPe.png

然後就完成了~~


上面的式子算到後面真的有點亂掉QQ~如果有覺得哪裡算得很怪可以再跟我說,我有空會看~
這邊也附上一個參考資訊[1],寫的真的非常詳細~也可以參考一下
明天將會利用python實現HMM+Viterbi 演算法來處理POS的任務~~

參考資訊
[1] Viterbi Algorithm


上一篇
[Day7] 詞性標注(二)-方法介紹
下一篇
[Day9] 詞性標注(四)-利用python實作POS任務
系列文
30天初步了解自然語言處理-自學筆記30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言